package Leetcode第一期;

public class 矩阵中的路径_12 {
    private boolean[][] marked;
    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; //分别对应上右下左
    // 盘面上有多少行
    private int m;
    // 盘面上有多少列
    private int n;
    private String word;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        this.m=board.length; //行
        this.n=board[0].length;  //列
        this.marked= new boolean[m][n]; //标记二维数组
        this.board=board;
        this.word=word;

        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                //找到开头的位置
                if (dfs(i,j,0)){
                    return true;
                }
            }
        }

        return false;
    }

    //递归
    private boolean dfs(int i, int j, int start) {
        //若为最后一个单词
        if (start == word.length() - 1) {
            return board[i][j] == word.charAt(start);
        }
        if (board[i][j]==word.charAt(start)){
            //若相等则进行方向判断,并记录当前位置为标记
            marked[i][j]=true;

            for (int k=0;k<4;k++){
                //构建新索引
                int newX=direction[k][0]+i;
                int newY=direction[k][1]+j;

                //四个方向 判断是否被标记，且是否在矩阵内
                if (isArea(newX,newY) && !marked[newX][newY]){
                    if (dfs(newX,newY,start+1)){
                        return true;
                    }
                }
            }
            marked[i][j]=false;
        }
        return false;
    }

    private boolean isArea(int newX, int newY) {
        return newX>=m && newX<0 && newY<0 && newY>=n;
    }

    /*public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        char tmp = board[i][j];
        board[i][j] = '/';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = tmp;
        return res;
    }*/

}
